package org.chnxi.leetcode.problems.ques18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 四数之和
 * 执行用时 :22 ms, 在所有 Java 提交中击败了34.32%的用户
 * 内存消耗 :39.9 MB, 在所有 Java 提交中击败了13.16%的用户
 * 参照ques15的思路编写，在nums中数量较多时，不可用
 */
public class Simple01 {

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        List<List<Integer>> result = fourSum(nums , 0);
        result.forEach(arr -> {
            arr.forEach(e -> {
                System.out.print(e+", ");
            });
            System.out.println();
        });
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();

        if(null == nums || nums.length < 4){
            return result;
        }

        Arrays.sort(nums);
        int len = nums.length;

        for (int num1Idx = 0; num1Idx < len-3; num1Idx++){
            if(num1Idx>0 && nums[num1Idx] == nums[num1Idx-1]){
                continue;
            }

            for (int num2Idx = num1Idx+1; num2Idx < len-2; num2Idx++){
                if(num2Idx > num1Idx+1 && nums[num2Idx] == nums[num2Idx-1]){
                    continue;
                }

                int num4Idx = len -1;

                for(int num3Idx = num2Idx+1; num3Idx < len-1; num3Idx++){
                    if(num3Idx > num2Idx+1 && nums[num3Idx] == nums[num3Idx-1]){
                        continue;
                    }

                    while (num4Idx > num3Idx && nums[num1Idx] + nums[num2Idx] + nums[num3Idx] + nums[num4Idx] > target){
                        num4Idx--;
                    }
                    if(num4Idx == num3Idx){
                        break;
                    }
                    if(nums[num1Idx] + nums[num2Idx] + nums[num3Idx] + nums[num4Idx] == target){
                        List<Integer> arr = new ArrayList<>();
                        arr.add(nums[num1Idx]);
                        arr.add(nums[num2Idx]);
                        arr.add(nums[num3Idx]);
                        arr.add(nums[num4Idx]);
                        result.add(arr);
                    }
                }
            }
        }
        return result;
    }
}
